1008. Construct Binary Search Tree from Preorder Traversal
Medium

Given an array of integers preorder, which represents the preorder traversal of a BST (i.e., binary search tree), construct the tree and return its root.

It is guaranteed that there is always possible to find a binary search tree with the given requirements for the given test cases.

A binary search tree is a binary tree where for every node, any descendant of Node.left has a value strictly less than Node.val, and any descendant of Node.right has a value strictly greater than Node.val.

A preorder traversal of a binary tree displays the value of the node first, then traverses Node.left, then traverses Node.right.

 

Example 1:

Input: preorder = [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]

Example 2:

Input: preorder = [1,3]
Output: [1,null,3]

 

Constraints:

  • 1 <= preorder.length <= 100
  • 1 <= preorder[i] <= 108
  • All the values of preorder are unique.
Accepted
168,202
Submissions
213,227
Seen this question in a real interview before?
Companies
Related Topics

Average Rating: 4.54 (43 votes)

Premium

Solution


Approach 1: Construct binary tree from preorder and inorder traversal

Intuition

This approach is not the optimal one because of O(NlogN)\mathcal{O}(N \log N) time complexity, but very straightforward.

Let's use here two facts:

Algorithm

  • Construct inorder traversal by sorting the preorder array.

  • Construct binary tree from preorder and inorder traversal: the idea is to peek the elements one by one from the preorder array and try to put them as a left or as a right child if it's possible. If it's impossible - just put null as a child and proceed further. The possibility to use an element as a child is checked by an inorder array: if it contains no elements for this subtree, then the element couldn't be used here, and one should use null as a child instead.

Implementation

bla

Complexity Analysis

  • Time complexity : O(NlogN)\mathcal{O}(N \log N). O(NlogN)\mathcal{O}(N \log N) to sort preorder array and O(N)\mathcal{O}(N) to construct the binary tree.
  • Space complexity : O(N)\mathcal{O}(N) the inorder traversal and the tree.



Approach 2: Recursion

Intuition

It's quite obvious that the best possible time complexity for this problem is O(N)\mathcal{O}(N) and hence the approach 1 is not the best one.

Basically, the inorder traversal above was used only to check if the element could be placed in this subtree. Since one deals with a BST here, this could be verified with the help of lower and upper limits for each element as for the validate BST problem. This way there is no need in inorder traversal and the time complexity is O(N)\mathcal{O}(N).

Algorithm

  • Initiate the lower and upper limits as negative and positive infinity because one could always place the root.

  • Start from the first element in the preorder array idx = 0.

  • Return helper(lower, upper):

    • If the preorder array is used up idx = n then the tree is constructed, return null.

    • If current value val = preorder[idx] is smaller then lower limit, or larger than upper limit, return null.

    • If the current value is in the limits, place it here root = TreeNode(val) and proceed to construct recursively left and right subtrees: root.left = helper(lower, val) and root.right = helper(val, upper).

    • Return root.

Implementation

bla

Complexity Analysis

  • Time complexity : O(N)\mathcal{O}(N) since we visit each node exactly once.
  • Space complexity : O(N)\mathcal{O}(N) to keep the entire tree.


Approach 3: Iteration

Algorithm

The recursion above could be converted into the iteration with the help of stack.

  • Pick the first preorder element as a root root = new TreeNode(preorder[0]) and push it into stack.

  • Use for loop to iterate along the elements of preorder array :

    • Pick the last element of the stack as a parent node, and the the current element of preorder as a child node.

    • Adjust the parent node : pop out of stack all elements with the value smaller than the child value. Change the parent node at each pop node = stack.pop().

    • If node.val < child.val - put the child as a right child of the node : node.right = child.

    • Else - as a left child : node.left = child.

    • Push child node into the stack.

  • Return root.

Implementation

Current
1 / 12

Complexity Analysis

  • Time complexity : O(N)\mathcal{O}(N) since we visit each node exactly once.

  • Space complexity : O(N)\mathcal{O}(N) to keep the stack and the tree.

Report Article Issue

Comments: 25
Sithis's avatar
Read More

Please stop using Stack class in Java. Here (leetcode.com/problems/flatten-nested-list-iterator/discuss/80147/Simple-Java-solution-using-a-stack-with-explanation/165585) you can find a great explanation of why it's a bad idea and it might even cost you an offer.
There's an unhealthy obsession with Stack and LinkedList classes on Leetcode - 2 classes that nobody uses in real life.

53
Show 14 replies
Reply
Share
Report
wangjian4814's avatar
Read More

why we can not just use insert method to creat a new BST, which is the answer?

10
Show 5 replies
Reply
Share
Report
miladinho's avatar
Read More

In approach 2, the use of the lower bound is not necessary at all. Surprised the author dares to write "It's quite obvious that the best possible time complexity for this problem is O(N) " but does not realize the "obvious" facts that:

  1. we have a BST
  2. we have a preorder of that BST

Meaning that because you are going left first by default tree traversal pattern, then you are guaranteed to have placed the least element first. So only need to check the upper limit.

class Solution {
  int idx = 0;
  int[] preorder;
  int n;

  public TreeNode helper(int upper) {
    // if all elements from preorder are used
    // then the tree is constructed
    if (idx == n) return null;

    int val = preorder[idx];
    // if the current element 
    // couldn't be placed here to meet BST requirements
    if (val > upper) return null;

    // place the current element
    // and recursively construct subtrees
    idx++;
    TreeNode root = new TreeNode(val);
    root.left = helper(val);
    root.right = helper(upper);
    return root;
  }

  public TreeNode bstFromPreorder(int[] preorder) {
    this.preorder = preorder;
    n = preorder.length;
    return helper(Integer.MAX_VALUE);
  }
}

"obvious" .... smh...

not really

11
Reply
Share
Report
zzznotsomuch's avatar
Read More

@andvary @liaison How come space complexity for Solution 3 is O(N)? While adding any new node, we might have to pop logN amount of node. Doesn't that make it O(NlogN)?

4
Show 2 replies
Reply
Share
Report
calvinchankf's avatar
Read More

Recall the basic question of BST, #701 Insert into a Binary Search Tree

Here was my 1st attempt in python

"""
1st: recursion
    - reuse lc701: Insert into a Binary Search Tree
    - for each element in the array
    - do lc701

    Time    from O(N) to O(NlogN), because the number of nodes of result tree < N during the construction of it
    Space   O(N)
    12 ms, faster than 99.45%
"""
class Solution(object):
    def bstFromPreorder(self, preorder):
        res = None
        for x in preorder:
            res = self.insertIntoBST(res, x)
        return res
    def insertIntoBST(self, root, val):
        if root == None:
            return TreeNode(val)
        if val < root.val:
            root.left = self.insertIntoBST(root.left, val)
        else:
            root.right = self.insertIntoBST(root.right, val)
        return root

Here was my second attempt with iteration

"""
    2nd: same concept but with iteration
    - reuse lc701: Insert into a Binary Search Tree
    - for each element in the array
    - do lc701

    Time    from O(N) to O(NlogN), because the number of nodes of result tree < N during the construction of it
    Space   O(N)
    20 ms, faster than 84.85%
"""
class Solution(object):
    def bstFromPreorder(self, preorder):
        res = None
        for x in preorder:
            res = self.insertIntoBST(res, x)
        return res

    def insertIntoBST(self, root, val):
        if root == None:
            return TreeNode(val)
        cur = root
        while True:
            if cur.val < val:
                if cur.right != None:
                    cur = cur.right
                else:
                    cur.right = TreeNode(val)
                    break
            else:
                if cur.left != None:
                    cur = cur.left
                else:
                    cur.left = TreeNode(val)
                    break
        return root

4
Show 1 reply
Reply
Share
Report
ltbtb_rise's avatar
Read More

Isn't it a bit overcomplicated of approach 1 to just get a O(NlogN) solution?

We can easily get a O(NlogN) solution with this:

class Solution {
public:
    TreeNode* bstFromPreorder(vector<int>& preorder) {
        return helper(preorder,0,preorder.size()-1);
    }
    
    TreeNode* helper(vector<int>& preorder, int i, int j)
    {
        if(i>j) return nullptr;
        if(i==j) return new TreeNode(preorder[i]);
        
        TreeNode* root=new TreeNode(preorder[i]);
        
        int k=i+1;
        while(k<=j && preorder[k]<preorder[i]) k++;
        root->left=helper(preorder,i+1,k-1);
        root->right=helper(preorder,k,j);
        return root;
    }
};

2
Show 2 replies
Reply
Share
Report
andrewquartey's avatar
Read More

In approach 2 we don't need to track lower and upper. We can only keep track of the upper. I stand to be corrected but this is what I did and it worked. The code is in Javascript:

var bstFromPreorder = function(preorder) {
    let i = 0
    
    function dfs(max){
        if(i == preorder.length) return null
        if(preorder[i] >= max) return null
        let root = new TreeNode(preorder[i])
        i++
        root.left = dfs(root.val)
        root.right = dfs(max)
        return root
    }
    return dfs(10e9)
};

1
Reply
Share
Report
blahblahblah23's avatar
nishadkumar's avatar
Read More

Approach 3 solution and animation is really good. Helps you understand in a very simple way. Thanks! :)

1
Reply
Share
Report
zzznotsomuch's avatar
Read More

Can someone explain how the complexity is O(N) for the third solution? To insert 10, for example, the code will pop 7 & 5 and thus it will do logN work. So the order should be O(NlogN) in worst case, right?

1
Show 1 reply
Reply
Share
Report
Success
Details
Runtime: 8 ms, faster than 44.03% of C++ online submissions for Construct Binary Search Tree from Preorder Traversal.
Memory Usage: 13.6 MB, less than 68.91% of C++ online submissions for Construct Binary Search Tree from Preorder Traversal.
Time Submitted
Status
Runtime
Memory
Language
06/21/2021 09:21Accepted8 ms13.6 MBcpp
06/21/2021 09:16Accepted4 ms12.6 MBcpp
07/10/2020 19:51Accepted4 ms10.9 MBcpp
/23
Contribute
|||
Saved
Trie
This list is empty.